1. Field of the Invention
The present invention relates to a branch predicting apparatus and a branch predicting method for predicting a branch in a pipeline processor, and more particularly, to a branch predicting apparatus and a branch predicting method capable of improving accuracy for predicting a branch target of a return instruction.
2. Description of the Related Art
Conventionally, a branch predicting method is widely used to accelerate a processing for a pipeline processor. When a branch is present in a program, it is originally necessary to stop a pipeline until the branch is confirmed. The processor that performs a branch prediction, however, predicts the branch and speculatively executes an instruction after the branch prediction.
The branch prediction carries a major advantage that a processing time until the branch is confirmed can be shortened. The branch prediction has, however, a major disadvantage that, when the prediction is missed, it is necessary to flash the pipeline and re-starts the processing at the branch instruction. Prediction accuracy is, therefore, quite important for the branch prediction.
A branch history is normally used for the branch prediction. The branch history is an apparatus that stores, as a history, a pair of an address of a previously executed branch instruction and an address of a branch target branched in response to the branch instruction. Since the branch prediction using the branch history is based on the history, it is effective when the same branch is repeated as in a loop processing. However, it is less effective for a return instruction from a sub-routine.
When a branch is produced in response to the return instruction from the sub-routine, the branch target is an instruction next to a call instruction in the sub-routine. Normally, however, the sub-routine is called from every location of the program, so that a return target of the return instruction is not fixed. As a result, even when the branch target is predicted according to the history, the prediction is not always correct.
Considering this, Japanese Patent Application Laid-open Publication No. 2001-172507 discloses a technique for storing a return address of a return instruction is stored in a return address stack when a call instruction from a sub-routine is executed, and making a prediction while giving a high priority on the return address stack over a branch history for the return instruction.
According to the technique disclosed in the above literature, the return address of the return instruction that corresponds to a call instruction is stored in the return address stack after execution of the call instruction is completed. Due to this, when the branch history detects the return instruction by an advance reading of an instruction sequence or the like before the execution of the call instruction is completed, the return address is not stored in the returns address stack.
If so, a previous return target stored in the branch history is predicted as the present return target. However, as already explained, the accuracy for the prediction based on the branch history is not high for the return instruction. Thus, the technique disclosed in the above literature has the problem that the branch prediction accuracy is deteriorated depending on a return-instruction detection timing.